题解 CF878C Tournament

发表于 | 更新于

题意:最近Berland开始了一场有k种运动的比赛。瓦萨亚希望在赌场上赚钱。 比赛的计划非常神秘，并没有完全公开。比赛选手背靠背举行，每场比赛都涉及两名尚未淘汰的运动员。每场比赛都可以举行k种运动里的任意一种，失败者则遭到淘汰。最后剩下的运动员成为冠军。除此之外，该方案可以是任意的，不提前公开。 瓦西亚了解各种运动中的运动员的力量。他认为，拥有更高力量的运动员总能获胜。 比赛每年举行一次，每年都有一名新参赛者加入比赛。在第一场比赛中，只有一名运动员参加，第二场比赛有两名运动员，依此类推。 请你帮助他找到每一年可能获得冠军的人数。

我们考虑两个选手之间的关系，如果一个选手能在任何一项运动中战胜对手，那么就从他自身向对手连一条有向边。这样显然会出现很多环，于是可以大力缩点，将整张图缩成一个$DAG$（实际实现中会变为一条链）。那么显然入度为零的环中包含的点数即为最后可能成为冠军的人数。

这里缩点的技巧就是这道题的关键，由于题目要求动态插入点，那么$tarjan$就不再适合了。于是我们可以选择$set$作为容器，把上述判断的条件重载成小于号，在$set$中用$find$查找（这里的$find$查找完全是根据$”<”$来的,即对于两个参数$a,b$,判断$==$的操作相当于判断$(!(a<b))$&&$(!(b<a)),)$是否有与当前选手可以合并的，并进行合并操作。合并后，我们的节点（即一个环）记录的是环中每项运动所有选手中的最大值和最小值，这样可以方便地进行环与环之间的比较。

将所有点插入后，答案即为$set$中的最后一个元素的大小，因为我们重载了小于号，所以最后一个节点都是“大于”之前的点的，在缩点后的图中一定是入度为$0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
using namespace std;
int n,k;
struct node{
    int mx[15],mn[15],size;
    friend bool operator <(node a,node b){
        for (int i=1;i<=k;++i)
            if (a.mx[i]>b.mn[i])return 0;
        return 1;
    }
}lxy;
set<node>s;
set<node>::iterator it;
inline int read(){
   int x=0,w=0;char ch=getchar();
   while (!isdigit(ch))w|=ch=='-',ch=getchar();
   while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
   return w?-x:x;
}
int main(){
    n=read(),k=read();
    for (int i=1;i<=n;++i){
        lxy.size=1;
        for (int j=1;j<=k;++j)lxy.mx[j]=lxy.mn[j]=read();
        it=s.find(lxy);
        while (it!=s.end()){
            lxy.size+=(*it).size;
            for (int j=1;j<=k;++j)
                lxy.mx[j]=max(lxy.mx[j],(*it).mx[j]),lxy.mn[j]=min(lxy.mn[j],(*it).mn[j]);
            s.erase(it);it=s.find(lxy);
        }
        s.insert(lxy);
        printf("%d\n",(*--s.end()).size);
    }
    return 0;
}